package com.cet.algorithm.数组;

/**
 * @program: cet-practice
 * @description: 二分查找
 * @author: 陈恩涛
 * @create: 2023-04-30 01:06
 **/
public class LC704 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 7, 9, 10};
        System.out.println(binarySearch2(arr, 8));
    }

    public static  int binarySearch(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length, target);
    }

    /**
     * [start, end]左闭右闭
     * @param nums 待查询数组
     * @param start 起始位置
     * @param end 结束位置
     * @param target 目标元素
     * @return 目标元素在查询数组中的下标
     */
    private static int binarySearch(int[] nums, int start, int end, int target) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > start) {
            return binarySearch(nums, start, mid - 1, target);
        } else {
            return binarySearch(nums, mid + 1, end, target);
        }
    }

    /**
     * [start, end) 左闭右开
     * @param nums 存放元素的数组
     * @param target 查找目标元素
     * @return 找到的元素下标或插入的位置
     */
    public static  int binarySearch2(int[] nums, int target) {
        int start = 0;
        int end = nums.length;
        while (start < end) {
             int mid = (start + end) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }
}
